from timeit import Timer
from Primes import Primes

import sys
import math


def Problem():
    """Euler published the remarkable quadratic formula:

        n^2 + n + 41

    It turns out that the formula will produce 40 primes for the consecutive 
    values n = 0 to 39. However, when n = 40, 40^(2) + 40 + 41 = 40(40 + 1) + 41
    is divisible by 41, and certainly when n = 41, 41^2 + 41 + 41 is clearly
    divisible by 41.

    Using computers, the incredible formula  n^2 - 79n + 1601 was discovered, 
    which produces 80 primes for the  consecutive values n = 0 to 79. The product
    of the coefficients, -79 and 1601, is -126479.
    
    Considering quadratics of the form:

        n^2 + an + b, where |a| < 1000 and |b| < 1000

        where |n| is the modulus/absolute value of n
        e.g. |11| = 11 and |-4| = 4

    Find the product of the coefficients, a and b, for the quadratic expression
    that produces the maximum number of primes for consecutive values of n,
    starting with n = 0.
    """

    #Get a list of primes    
    primes = set(Primes(1000))
    
    #Init value
    result = (0, 0, -1)
    for b in filter(lambda x: x <= 1000, primes):
        for a in xrange(-999, 1000):
            n = 0
            for n in xrange(0, b - a):
                f = n*n + a * n + b
                if f not in primes:
                    break
            
            if n > result[2]:
                result = (a, b, n)
        
    print "a, b, n = (%d, %d, %d)" % result
    ans = result[0] * result[1]

    
    print "Answer for Problem 27 = %s " % (ans,)


    
if __name__ == "__main__":
    t = Timer(setup='from __main__ import Problem', stmt='Problem()').timeit(1)
    print "Execution time = %0.3f seconds" %(t,)
